/**
 * SkipArrayList.java
 * @author: liuex
 * 2008-3-9 ����08:28:39
 *
 * note: 
 */
package org.lex.tf;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * Immuteable
 */
public class ArraySkipList<T> implements SkipList<T>
{
	private T[] array = null;
	private int[] skips = null;
	private int minIndex = 0;
	private int maxIndex = 0;
	private int size = 0;

	public ArraySkipList( T[] array, int ... skips )
	{
		this.initialize( array, skips );
	}

	@SuppressWarnings("unchecked")
	public ArraySkipList( SkipList<T> src, int ... skips )
	{
		if( src instanceof ArraySkipList )
		{
			ArraySkipList<T> asl = (ArraySkipList<T>) src;
			int[] newSkips = new int[ asl.skips.length +  skips.length ];
			System.arraycopy( asl.skips, 0, newSkips, 0, asl.skips.length );
			System.arraycopy( skips, 0, newSkips, asl.skips.length, skips.length );
			this.initialize( asl.array, newSkips );
		}
		else
		{

			this.initialize( src.toArray(), skips );
		}
	}
	
	private void initialize( T[] array, int[] skips )
	{
		this.array = array;
		this.skips = skips;
		this.size = array.length - skips.length;
		Arrays.sort( skips );
		this.minIndex = skips[0];
		this.maxIndex = skips[skips.length - 1];
	}

	@Override
	public T get( int index )
	{
		if( index < minIndex )
			return array[index];
		else if( index >= maxIndex )
			return array[index + skips.length];
		else
		{
			int i = Arrays.binarySearch( skips, index );
			if( i >= 0 )
				return array[index + i + 1];
			else
			{
				// index not found in skips
				return array[index - i + 1];
			}
		}
	}

	@Override
	public int size()
	{
		return this.size;
	}

	@SuppressWarnings( "unchecked" )
	@Override
	public T[] toArray()
	{
		T[] a = (T[]) Array.newInstance( array[0].getClass(), this.size );
		for( int i = 0; i < this.size(); i++ )
			a[i] = this.get( i );
		return a;
	}
}
